/*
 有两个数组A[n], B[m], n<m, A中的n个元素互不相同，对B中的每一个元素，
 都从A中随机取一个元素放入其中， 求A中的n个元素在B中都出现的概率 

 http://groups.google.com/group/pongba/browse_thread/thread/8070f78ce7f5d2b6
 */

#include "junix.h"
using namespace std;

uint64_t factor(uint64_t n) {
	if (n<=0) return 0;
	uint64_t result = 1;
	for (uint64_t i=1;i<=n;i++)
		result *= i;

	return result;
}

//C_m^n
uint64_t cnm(uint64_t m, uint64_t n) {
	uint64_t p=1,q=1;
	for (uint64_t i=1;i<=n;i++) {
		p *= (m+1-i);
		q *= i;
	}

	return p/q;
}

uint64_t f(uint64_t n, uint64_t m) {
	typedef  std::vector<std::vector<uint64_t> > MATRIX;
	MATRIX matrix(m+1,std::vector<uint64_t>(m+1,0));

	for(uint64_t i=1;i<=m;i++) {
		matrix[1][i] = 1;
		matrix[i][i] = factor(i);
	}

	for (uint64_t j=1;j<=m;j++) {
		for (uint64_t i=2;i<j;i++) {
			uint64_t result = 0;
			for (uint64_t k=1;k<=j-i+1;k++) {
				//result += f(n-1,m-i)*cnm(m,i);
				result += matrix[i-1][j-k]*cnm(j,k);
			}
			matrix[i][j] = result;
		}
	}

	return matrix[n][m];
}

int main(int argc, char **argv)
{
	cout<<numeric_limits<unsigned long long>::max()<<endl;
	cout<<f(2,3)<<endl;
	cout<<f(3,4)<<endl;
	cout<<f(25,26)<<endl;
	cout<<f(15,26)<<endl;
}
